An important role of testing VLSI circuit designs is to identify redundant faults in the design. A redundant fault is a fault that has no effect on the circuit behavior with respect to the output of the circuit, although its presence can add unnecessarily to the silicon area of the circuit or slow its performance. However, a redundant fault typically cannot be recognized a priori and the process of generating a test generally serves to identify such a fault. It is important to identify redundant faults in a design both to avoid the need for testing for them in the product of manufacture but also because their identification sometimes is useful to a redesign that will improve the cost performance of the circuit.
Many practical VLSI circuits typically include non-Boolean primitives like tri-state buffers, bidirectional buffers and bus configurations. Some test generation systems use logic models for non-Boolean gates. These models, though accurate, are very pessimistic and often fail to find tests. A realistic modeling of these primitives for test generation or logic simulation requires the use of Boolean logic values like 0 or 1 and additional non-Boolean logic values like the high-impedance state (Z). In the past, at least five values have been used for test generation: 0, 1, Z, U and X. The value X denotes a yet unspecified signal value and U denotes an unknown value. For example, if an OR gate has a value Z (or U) at one input and values 0 at all other inputs, then the output assumes the value U. Test generation for combinational circuits with non-Boolean primitives is significantly more complex than circuits with only Boolean primitives due to the additional non-Boolean values. For example, a recent paper by J. Van der Hinden et al entitled "Test Generation and Three-State Elements, Buses and Bidirectionals," in VLSI Test Symposium, pp. 114-121, April 1994, describes a 25-value logic system for generating tests for production circuits that include non-Boolean components. In this application, we refer to circuits which may include both Boolean and non-Boolean components generically as production circuits. The term combinational circuits is used for circuits that include only Boolean logic gates.
Methods using energy minimization, Boolean satisfiability (described in a paper by T. Larrabee entitled "Test Generation Using Boolean Satisfiability" in IEEE Trans. on Computer-Aided Design, vol. 11, pp. 4-15, January 1992) and Binary Decision Diagram (BDD-based) (described in a paper entitled by T. Stanion and D. Bhattacharya entitled "TSUNAMI: A Path Oriented Scheme for Algebraic Test Generation," in Proc. of the 21st IEEE Inter. Syrup. on Fault Tolerant Computing, pp. 36-43, June 1991) formulations have been recently proposed for generating tests for combinational circuits. The teachings of these prior art references are incorporated herein by reference. These methods are fast and practical for testing large combinational circuits and share the following similarities: (1) they represent logic values on signals by Boolean variables, (2) they construct energy functions or satisfiability expressions using these Boolean variables and (3) they solve the energy minimization or the satisfiability problem to obtain a set of Boolean values for the variables and this set corresponds to a test for the fault. An example of the energy minimization approach is described in U.S. Pat. No. 5,377,201 that issued on Dec. 27, 1994 and the teaching of this patent is incorporated herein by reference. Extending these formulations to production circuits is non-trivial for the following reasons: (1) signals can assume more than two values (for example, a tri-state buffer can assume the high-impedance state) and two or more Boolean variables are required to represent the additional logic values of a signal,(2) new and more complex energy functions and satisfiability expressions have to be designed for all Boolean and non-Boolean primitives in the circuit, and (3) the additional Boolean variables significantly increase the search space of the test generation problem, and this can render the new formulation expensive to test for large designs.
The present invention describes a systematic methodology for modifying combinational test generation algorithms for use with production circuits. We also describe the use of the proposed methodology for identifying and removing redundancies in production circuits.